package leetcode;

import leetcode.util.TreeNode;

/**
 * Created by tiang on 2018/9/4.
 * Given a non-empty binary tree, find the maximum path sum.

 For this problem, a path is defined as any sequence of nodes from some starting node to any
 node in the tree along the parent-child connections. The path must contain at least one node
 and does not need to go through the root.

 Example 1:

 Input: [1,2,3]

 1
 / \
 2   3

 Output: 6
 Example 2:

 Input: [-10,9,20,null,null,15,7]

 -10
 / \
 9  20
 /  \
 15   7

 Output: 42
 */
public class TreeMaximumPath {
    /**
     * 存储每个节点的单条路径最大值depth以及最大路径maxVal
     */
    static class Pair{
        public int maxVal;
        public int depth;
        public Pair(int m,int d){
            this.maxVal = m;
            depth = d;
        }
    }
    public int maxPathSum(TreeNode root) {
        return maxPathSumSub(root).maxVal;
    }

    /**
     * 求当前节点的Pair
     * @param root 当前节点
     * @return 当前节点的单条路径最大值以及最大路径值
     */
    private Pair maxPathSumSub(TreeNode root) {
        // 如果子节点为空则返回空
        if (root == null)
            return null;
        // 求左右节点的pair
        Pair left = maxPathSumSub(root.left),
                right = maxPathSumSub(root.right);
        int val = root.val;
        // 如果左右节点都为空在，则返回当前节点
        if(left == null && right == null)
            return new Pair(val, val);
        else if(left!=null && right!=null) {
            int depth = Integer.max(left.depth, right.depth) + val;
            depth = Integer.max(depth, val);
            int max = Integer.max(Integer.max(left.depth + right.depth + val, left.maxVal),
                    right.maxVal);
            max = Integer.max(max, left.depth + val);
            max = Integer.max(max, right.depth + val);
            max = Integer.max(max, val);
            return new Pair(max, depth);
        }else{
            Pair temp = left == null ?right:left;
            int depth = Integer.max(temp.depth+val, val);
            int max = Integer.max(temp.depth+val, temp.maxVal);
            max = Integer.max(max, val);
            return new Pair(max, depth);
        }
    }
}
